#include <iostream>
using namespace std;
#include <vector> 



int process(vector<int>& w , vector<int>& v , int index , int bag)
{
  if (bag < 0 )
  {
    return -1;
  }

  if (index == static_cast<int>(w.size()))
  {
    return 0;
  }

  int p1 = process(w , v , index + 1 , bag);
  int p2 = 0;
  int next = process(w , v ,index + 1 , bag - w[index]);

  if (next != -1)
  {
    p2 = v[index] + next;
  }

  return  max(p1 , p2);
}


int process1(vector<int>& w , vector<int>& v , vector<vector<int>>& dp , int bag)
{
  // index 0 ~ w.size 
  // bag 0 ~ bagmax
  for (int col = 0; col < bag + 1; col++)
  {
    dp[w.size()][col] = 0;
  }

  for (int dpindex = w.size() - 1 ; dpindex >= 0  ; dpindex--)
  {
    for(int dpbag = 0; dpbag <= bag ; dpbag++)
    {
      int p1 = dp[dpindex + 1][dpbag];
      int p2 = 0;
      if (dpbag - w[dpindex] >= 0)
      {
        p2 = v[dpindex] + dp[dpindex+1][bag - w[dpindex]];
      }

      dp[dpindex][dpbag] = max(p1 , p2);
    }
  }

  return dp[0][bag];
}


int main()
{
  vector<int> weight = {3 , 2, 4 ,7 , 3, 1, 7};
  vector<int> vlaue = {5 , 6, 3 ,19 , 12, 4 , 2};

  int bag = 15;
  vector<vector<int>> dp(static_cast<int>(weight.size() + 1) , vector<int>(bag + 1));
  int ret  =  process1(weight , vlaue , dp , bag);

  cout << ret << endl;
  return 0;
}
